|
: ''For other uses, see Chinese restaurant (disambiguation).'' In probability theory, the Chinese restaurant process is a discrete-time stochastic process, analogous to seating customers at tables in a Chinese restaurant. Imagine a Chinese restaurant with an infinite number of circular tables, each with infinite capacity. Customer 1 is seated at an unoccupied table with probability 1. At time ''n'' + 1, a new customer chooses uniformly at random to sit at one of the following ''n'' + 1 places: directly to the left of one of the ''n'' customers already sitting at an occupied table, or at a new, unoccupied table. At time ''n'', the value of the process is a partition of the set of ''n'' customers, where the tables are the blocks of the partition. Mathematicians are interested in the probability distribution of this random partition. David J. Aldous attributes the restaurant analogy to Jim Pitman and Lester Dubins in his 1983 book. == Formal definition == At any positive-integer time ''n'', the value of the process is a partition ''B''''n'' of the set , whose probability distribution is determined as follows. At time ''n'' = 1, the trivial partition is obtained with probability 1. At time ''n'' + 1 the element ''n'' + 1 is either: # added to one of the blocks of the partition ''B''''n'', where each block is chosen with probability |''b''|/(''n'' + 1) where |''b''| is the size of the block, or # added to the partition ''B''''n'' as a new singleton block, with probability 1/(''n'' + 1). The random partition so generated has some special properties. It is ''exchangeable'' in the sense that relabeling does not change the distribution of the partition, and it is ''consistent'' in the sense that the law of the partition of ''n'' − 1 obtained by removing the element ''n'' from the random partition at time ''n'' is the same as the law of the random partition at time ''n'' − 1. The probability assigned to any particular partition (ignoring the order in which customers sit around any particular table) is : where ''b'' is a block in the partition ''B'' and |''b''| is the size (i.e. number of elements) of ''b''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Chinese restaurant process」の詳細全文を読む スポンサード リンク
|